#include <bits/stdc++.h>
// #include <ext/pb_ds/assoc_container.hpp>
// #include <ext/pb_ds/hash_policy.hpp>
// #include <ext/pb_ds/tree_policy.hpp>
#define ps putchar(' ')
#define pe putchar('\n')
#define int long long
#define eb emplace_back
#define pi pair<int, int>
#define mk make_pair
#define fi first
#define se second
#define Ad tr[p].ad
// #define Ad t[p].ad
#define ls p << 1
#define rs p << 1 | 1
// #define ls tr[p].son[0]
// #define rs tr[p].son[1]
// #define ls t[p].son[0]
// #define rs t[p].son[1]
#define len (r - l + 1)
#define mid ((l + r) >> 1)
using namespace std;
namespace Fread {
const int FAST_IO_SIZE = 16;
char FREAD_BUF[FAST_IO_SIZE], *FREAD_S, *TYPENNAME_T;
inline char getchar() {
    if (FREAD_S == TYPENNAME_T) {
        TYPENNAME_T = (FREAD_S = FREAD_BUF) + fread(FREAD_BUF, 1, FAST_IO_SIZE, stdin);
        if (FREAD_S == TYPENNAME_T) return '\n';
    }
    return *FREAD_S++;
}
}
namespace Fwrite {
const int FAST_IO_SIZE = 65536;
char FREAD_BUF[FAST_IO_SIZE], *FREAD_S = FREAD_BUF, *TYPENNAME_T = FREAD_BUF + FAST_IO_SIZE;
inline void flush() {
    fwrite(FREAD_BUF, 1, FREAD_S - FREAD_BUF, stdout);
    FREAD_S = FREAD_BUF;
}
inline void putchar(char FAST_IO_CHARC) {
    *FREAD_S++ = FAST_IO_CHARC;
    if (FREAD_S == TYPENNAME_T) flush();
}
struct NTR {
    ~ NTR() { flush(); }
} ztr;
}
#ifdef ONLINE_JUDGE
    #define getchar Fread :: getchar
    #define putchar Fwrite :: putchar
#endif
namespace Fastio {
struct Reader {
    template<typename TYPENNAME_T>
    Reader& operator >> (TYPENNAME_T& WRITER_ANYX) {
        char FAST_IO_CHARC = getchar();
        TYPENNAME_T FLAG = 1;
        while (FAST_IO_CHARC < '0' || FAST_IO_CHARC > '9') {
            if (FAST_IO_CHARC == '-') FLAG = -1;
            FAST_IO_CHARC = getchar();
        }
        WRITER_ANYX = 0;
        while (FAST_IO_CHARC >= '0' && FAST_IO_CHARC <= '9') {
            WRITER_ANYX = (WRITER_ANYX * 10 + (FAST_IO_CHARC - '0'));
            FAST_IO_CHARC = getchar();
        }
        WRITER_ANYX *= FLAG;
        return *this;
    }
    Reader& operator >> (char& FAST_IO_CHARC) {
        FAST_IO_CHARC = getchar();
        while (FAST_IO_CHARC == '\n' || FAST_IO_CHARC == ' ') FAST_IO_CHARC = getchar();
        return *this;
    }
    Reader& operator >> (char* STRINGSTR) {
        int READER_READLEN = 0;
        char FAST_IO_CHARC = getchar();
        while (FAST_IO_CHARC == '\n' || FAST_IO_CHARC == ' ') FAST_IO_CHARC = getchar();
        while (FAST_IO_CHARC != '\n' && FAST_IO_CHARC != ' ') {
            STRINGSTR[READER_READLEN++] = FAST_IO_CHARC;
            FAST_IO_CHARC = getchar();
        }
        STRINGSTR[READER_READLEN] = '\0';
        return *this;
    }
    Reader(){}
} cin;
const char endl = '\n';
struct Writer {
    template<typename TYPENNAME_T>
    Writer& operator << (TYPENNAME_T WRITER_ANYX) {
        if (WRITER_ANYX == 0) { putchar('0'); return *this; }
        if (WRITER_ANYX < 0) { putchar('-'); WRITER_ANYX = -WRITER_ANYX; }
        static int STACKTOP[45];
        int WRITER_BUF_TOP = 0;
        while (WRITER_ANYX) { STACKTOP[++WRITER_BUF_TOP] = WRITER_ANYX % 10; WRITER_ANYX /= 10; }
        while (WRITER_BUF_TOP) { putchar(STACKTOP[WRITER_BUF_TOP] + '0'); --WRITER_BUF_TOP; }
        return *this;
    }
    Writer& operator << (char FAST_IO_CHARC) {
        putchar(FAST_IO_CHARC);
        return *this;
    }
    Writer& operator << (char* STRINGSTR) {
        int WRITER_CURR = 0;
        while (STRINGSTR[WRITER_CURR]) putchar(STRINGSTR[WRITER_CURR++]);
        return *this;
    }
    Writer& operator << (const char* STRINGSTR) {
        int WRITER_CURR = 0;
        while (STRINGSTR[WRITER_CURR]) putchar(STRINGSTR[WRITER_CURR++]);
        return *this;
    }
    Writer(){}
} cout;
}
#define cin Fastio :: cin
#define cout Fastio :: cout
#define endl Fastio :: endl
// using namespace __gnu_pbds
inline int read()
{
    int f = 0, ans = 0;
    char c = getchar();
    while (!isdigit(c))
        f |= c == '-', c = getchar();
    while (isdigit(c))
        ans = (ans << 3) + (ans << 1) + c - 48, c = getchar();
    return f ? -ans : ans;
}
void write(int x)
{
    if (x < 0)
        putchar('-'), x = -x;
    if (x > 9)
        write(x / 10);
    putchar(x % 10 + '0');
}
const int N = 1e5 + 5, M = N << 2, inf = 1e18, mod = 998244353;
int n, m, ans, col[N];
int d[N], in[N], vis[N];
vector<int> g[N], full[N], id[N];
void zero(int u) {
	if(vis[u])	return;
	vis[u]=1;
	for(int &v:g[u]) { zero(v); return; }
}
bool circle(int u,int col) {
	vis[u]=col;
	for(int &v:g[u])
		if(!vis[v]) {
			if(circle(v, col))	return 1;
		}
		else if(vis[v]==col)	return 1;
	return 0;
}
void color(int u,int c) {
	vis[u]=1, col[u]=c;
	for(int &v:full[u])
		if(!vis[v])	color(v, c);
}
signed main()
{
	// ++
	// ++
	// ++
	// ++
	// ++
	// ++
	// ++
	// ++
	// ++
	// ++
	// ++
	// ++
	// ++
	// ++
	// ++
	// ++
	// ++
	// ++
	// ++
	// ++
	// ++
	// ++
	// ++
	// ++
	// ++
	// ++
	// ++
	// ++
	// ++
	// ++
	// ++
	// ++
	// ++
	// ++
	// ++
	// ++
	// ++
	// ++
	// ++
	// ++
	// ++
	// ++
	// ++
	// ++
	// ++
	// ++
	// ++
	// ++
	// ++
	// ++
	// ++
	// ++
	// ++
	// ++
	// ++
	// ++
	// ++
	// ++
	// ++
	// ++
	// ++
	// ++
	// ++
	// ++
	// ++
	// ++
	// ++
	// ++
	// ++
	// ++
	// ++
	// ++
	// ++
	// ++
	// ++
	// ++
	// ++
	// ++
	// ++
	// ++
	// ++
	// ++
	// ++
	// ++
	// ++
	// ++
	// ++
    freopen("circ.in", "r", stdin);
    freopen("circ.out", "w", stdout);
	int T; cin>>T;
	while(T--) {
		cin>>n>>m;
		fill(d+1, d+n+1, 0);
		fill(in+1, in+n+1, 0);
		fill(vis+1, vis+n+1, 0);
		fill(col+1, col+n+1, 0);
		for(int i=1;i<=n;++i)	g[i].clear(), full[i].clear(), id[i].clear();
		int z=0;
		while(m--) {
			int u=read()+1, v=read()+1;
			g[u].eb(v), ++in[v];
			full[u].eb(v), full[v].eb(u);
			if(u==v)	z=1;
		}
		auto check_zero=[]() {
			zero(1);
			for(int i=1;i<=n;++i)
				if(!vis[i]) {
					fill(vis+1, vis+n+1, 0);
					return 0;
				}
			fill(vis+1, vis+n+1, 0);
			return 1;
		};
		auto check_circle=[]() {
			for(int i=1;i<=n;++i)
				if(!vis[i] && circle(i, i))	return 1;
			fill(vis+1, vis+n+1, 0);
			return 0;
		};
		if(!z && check_zero()) { puts("0"); continue; }
		else if(check_circle()) { write(n-1), pe; continue; }
		for(int i=1;i<=n;++i)
			if(!vis[i])	color(i, i);
		fill(vis+1, vis+n+1, 0);
		for(int i=1;i<=n;++i)	id[col[i]].eb(i);
		ans=0;
		for(int c=1;c<=n;++c)
			if(!id[c].empty()) {
				queue<int> q;
				for(int &i:id[c])
					if(!in[i])	d[i]=1, q.push(i);
				while(!q.empty()) {
					int u=q.front();
					q.pop();
					for(int &v:g[u]) {
						if(!d[v])	d[v]=d[u]+1;
						if(--in[v]==0)	q.push(v);
					}
				}
				ans+=1+id[c].size();
				for(int &i:id[c])
					if(++vis[d[i]]==1)	--ans;
				for(int &i:id[c])	--vis[d[i]];
			}
		write(ans), pe;
	}
    return 0;
}
